package com.xuyuan.arithmetic.datastructure.quest;

import org.junit.jupiter.api.Test;

import java.util.InputMismatchException;
import java.util.Scanner;

/**
 * 动态规划算法案例
 *
 * @author xuyuan
 * @desc 动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的.
 * @step 对于动态规划问题，拆解为如下五步曲
 * <p> 确定dp数组（dp table）以及下标的含义
 * <p> 确定递推公式
 * <p> dp数组如何初始化
 * <p> 确定遍历顺序
 * <p> 举例推导dp数组，打印动态规划的dp数组，验证结果
 */
public class DPSolution {

    /**
     * @desc 斐波那契数列
     * <p>
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
     * <p>
     * 示例:
     * F(2) = F(1) + F(0) = 1 + 0 = 1
     * F(3) = F(2) + F(1) = 1 + 1 = 2
     * F(4) = F(3) + F(2) = 2 + 1 = 3
     */
    int fib1(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++) {
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }

    int fib2(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    /**
     * @desc 爬楼梯
     * <p>
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 注意：给定 n 是一个正整数。
     * <p>
     * 示例 1：
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1 阶 + 1 阶
     * 2 阶
     * <p>
     * 示例 2：
     * 输入： 3
     * 输出： 3
     * 解释： 有三种方法可以爬到楼顶。
     * 1 阶 + 1 阶 + 1 阶
     * 1 阶 + 2 阶
     * 2 阶 + 1 阶
     * <p>
     * @step 五步
     * <p> dp[i]： 爬到第i层楼梯，有dp[i]种方法
     * <p> dp[i] = dp[i - 1] + dp[i - 2]
     * <p> dp[1] = 1，dp[2] = 2
     * <p> 从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
     * <p> 举例当n为5的时候，dp table（dp数组）[1,2,3,5,8]
     */
    int climbStairs1(int n) {
        if (n < 3) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    int climbStairs2(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2, sum;
        for (int i = 3; i <= n; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }

    /**
     * @desc 使用最小花费爬楼梯
     * <p>
     * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
     * 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
     * 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
     * <p>
     * 示例 1：
     * 输入：cost = [10, 15, 20]
     * 输出：15
     * 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
     * <p>
     * 示例 2：
     * 输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
     * 输出：6
     * 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
     * <p>
     * 提示：
     * cost 的长度范围是 [2, 1000]。
     * cost[i] 将会是一个整型数据，范围为 [0, 999] 。
     * <p>
     * @step 五步
     * <p> dp[i]： 爬到第i层楼梯，最小花费
     * <p> dp[i] = Math.min(dp[i - 1]+cost[i-1], dp[i - 2]+cost[i-2])
     * <p> dp[1] = 0，dp[2] = 0,dp[3] = Math.min(dp[2]+cost[2], dp[1]+cost[1])
     * <p> 顺序遍历
     * <p> 举例当n为5的时候，dp table（dp数组）[1,2,3,5,8]
     */
    int minCostClimbingStairs(int[] cost) {
        if (cost.length == 0) return 0;
        if (cost.length == 1) return cost[0];
        if (cost.length == 2) return Math.min(cost[0], cost[1]);
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }

    /**
     * @desc 不同路径
     * <p>
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     * 问总共有多少条不同的路径？
     * <p>
     * 示例 1：
     * 输入：m = 3, n = 7
     * 输出：28
     * 示例 2：
     * <p>
     * 输入：m = 2, n = 3
     * 输出：3
     * 解释： 从左上角开始，总共有 3 条路径可以到达右下角。
     * <p>
     * 向右 -> 向右 -> 向下
     * 向右 -> 向下 -> 向右
     * 向下 -> 向右 -> 向右
     * 示例 3：
     * <p>
     * 输入：m = 7, n = 3
     * 输出：28
     * 示例 4：
     * <p>
     * 输入：m = 3, n = 3
     * 输出：6
     * @step 步骤
     * <p> dp[i][j]：到达第i行第j列的路径总数
     * <p> dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * <p> dp[0][j] = 1,dp[i][0]=1;
     * <p> 顺序
     * <p> 举例验证
     */
    int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     * <p>
     * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     * 输出：2
     * 输入：obstacleGrid = [[0,1],[0,0]]
     * 输出：1
     * <p>
     * 提示：
     * m == obstacleGrid.length
     * n == obstacleGrid[i].length
     * 1 <= m, n <= 100
     * obstacleGrid[i][j] 为 0 或 1
     * <p>
     * 有障碍的路径为 0
     */
    int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        // 如果在起点或终点出现了障碍，直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        // 有障碍的后续节点都是0
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        // 这个循环的终止条件和上述循环不一致，上述在obstacleGrid[i][0] ！= 0 循环就会终止
        // for (int i = 0; i < m  ; i++) {
        //     if (obstacleGrid[i][0] == 0) dp[i][0] = 1;
        // }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * @desc 拆分整数
     * <p>
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     * <p>
     * 示例 1:
     * <p>
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1。
     * 示例 2:
     * <p>
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     * 说明: 你可以假设 n 不小于 2 且不大于 58
     * <p>
     * dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j])) 递推公式：
     * 假设我们有一个长度为 i 的绳子，我们需要将其切成若干段，使得这些段的乘积最大。我们可以尝试在每个可能的位置 j 处切割绳子，然后比较以下两种情况：
     * 直接切割成两段：j * (i - j)，即不进一步切割 i - j 这一段。
     * 切割成两段后，继续对 i - j 进行最优切割：j * dp[i - j]，即对 i - j 这一段继续应用动态规划的思想，找到其最优解。
     * 最终，我们在所有可能的 j 处取这两种情况的最大值，并更新 dp[i]。
     */
    int integerBreak(int n) {
        // dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i - j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                // 并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                // j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                // 而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }

    /**
     * @desc 不同的二叉搜索树
     * <p>
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种
     * <p>
     * 二叉搜索树是一个有序树：
     * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
     * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
     * 它的左、右子树也分别为二叉搜索树
     * 这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。
     * <p>
     * 画图，写案例，举例写递推公式。
     */
    int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // 对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                // 一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                // 左子树小于j（j-1），右子树大于j（i-j）
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    /**
     * @desc 0-1背包问题
     * <p>
     * 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
     * 回溯时间复杂度高，使用动态规划优化。
     * 单元测试不支持System.in
     */
    static void packBasicProblem() {
        try (Scanner scanner = new Scanner(System.in)) {
            // 物品数量
            int n = scanner.nextInt();
            // 背包最大承受重量
            int bagweight = scanner.nextInt();

            // 输入验证
            if (n <= 0 || bagweight < 0) {
                throw new InputMismatchException("数量或者最大承重不合法");
            }

            int[] weight = new int[n];
            int[] value = new int[n];

            // 第i个物品质量
            for (int i = 0; i < n; ++i) {
                weight[i] = scanner.nextInt();
                if (weight[i] < 0) {
                    throw new InputMismatchException("Weight cannot be negative");
                }
            }

            for (int j = 0; j < n; ++j) {
                value[j] = scanner.nextInt();
                if (value[j] < 0) {
                    throw new InputMismatchException("Value cannot be negative");
                }
            }

            int[][] dp = new int[n][bagweight + 1];
            for (int j = weight[0]; j <= bagweight; j++) {
                dp[0][j] = value[0];
            }

            for (int i = 1; i < n; i++) {
                for (int j = 0; j <= bagweight; j++) {
                    if (j < weight[i]) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                    }
                }
            }
            System.out.println(dp[n - 1][bagweight]);

            // 优化空间复杂度为 O(bagweight)
            // int[] dp = new int[bagweight + 1];
            //
            // for (int i = 0; i < n; i++) {
            //     for (int j = bagweight; j >= weight[i]; j--) {
            //         dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            //     }
            // }
            // System.out.println(dp[bagweight]);
        } catch (InputMismatchException e) {
            System.out.println("Invalid input: " + e.getMessage());
        }
    }

    /**
     * @desc 分割等和子集
     * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
     * <p>
     * 示例 1:
     * <p>
     * 输入: [1, 5, 11, 5]
     * 输出: true
     * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
     * 示例 2:
     * <p>
     * 输入: [1, 2, 3, 5]
     * 输出: false
     * 解释: 数组不能分割成两个元素和相等的子集.
     */
    boolean canPartition(int[] nums) {
        return true;
    }

    @Test
    public void test() {
        // System.out.println(minCostClimbingStairs(new int[]{1, 100, 1, 1}));
        // System.out.println(uniquePaths(3, 3));
        int[][] obstacleGrid = {{0, 1, 0}, {1, 0, 0}, {0, 0, 0}};
        System.out.println(uniquePathsWithObstacles(obstacleGrid));
    }

    public static void main(String[] args) {
        // packBasicProblem();
        System.out.println("5" + 2);
    }

}
